package com.wss.lsl.test.driven.arithmetic.sort;

/**
 * 合并排序
 * 
 * @author weiss
 *
 */
public class MergeSort {

	public static void sort(int[] data, int p, int r) {
		if (p < r) {
			int q = (p + r) / 2;

			sort(data, p, q);
			sort(data, q + 1, r);

			merge(data, p, q, r);
		}
	}

	private static void merge(int[] data, int p, int q, int r) {

		int n1 = q - p + 1;
		int n2 = r - q;
		int[] L = new int[n1 + 1];
		int[] R = new int[n2 + 1];

		for (int i = 0; i < n1; i++) {
			L[i] = data[p + i];
		}
		for (int i = 0; i < n2; i++) {
			R[i] = data[q + 1 + i];
		}

		L[n1] = Integer.MAX_VALUE;
		R[n2] = Integer.MAX_VALUE;

		int k = p;
		int i = 0;
		int j = 0;
		while (k <= r) {
			if (L[i] <= R[j]) {
				data[k] = L[i];
				i++;
			} else {
				data[k] = R[j];
				j++;
			}
			k++;
		}
	}
}
